package com.leetcode.No0769;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 最多能完成排序的块
 * @author: Wang Zhihua
 * @date: 2022-10-13
 */
public class Solution {
    public int maxChunksToSorted(int[] arr) {
        int len = arr.length;
        int count = 0;
        int flag = 11;
        int ans = 0;
        while (count < len) {
            int idx = 0;
            while (arr[idx] > 10) {
                ++idx;
            }
            while (arr[idx] < 10) {
                int tmp = arr[idx];
                arr[idx] = flag;
                idx = tmp;
                ++count;
            }
            int a = 0, b = len - 1;
            while (arr[a] != flag) {
                ++a;
            }
            while (arr[b] != flag) {
                --b;
            }
            int tmp = 0;
            for (int i = a; i <= b; ++i) {
                if (arr[i] == flag) {
                    ++tmp;
                }
            }
            if (tmp == b - a + 1) {
                ++ans;
            }
        }
        return ans;
    }

    @Test
    public void test1() {
        int[] arr = new int[]{4,3,2,1,0};
        System.out.println(this.maxChunksToSorted(arr));

        arr = new int[]{1,0,2,3,4};
        System.out.println(this.maxChunksToSorted(arr));
    }
}
